package Q744;

import java.util.Arrays;

class Solution3 {
    public char nextGreatestLetter(char[] letters, char target) {
        StringBuilder sb = new StringBuilder();
        for (char c : letters) {
            sb.append(c);
        }
        sb.append(target);

        char[] chars = sb.toString().toCharArray();
        Arrays.sort(chars);

        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == target && i != chars.length - 1 && chars[i + 1] != target) {
                return chars[i + 1];
            }
        }
        return chars[0];
    }
}

class Solution2 {
    public char nextGreatestLetter(char[] letters, char target) {
        int length = letters.length;
        if (target >= letters[length - 1]) {
            return letters[0];
        }
        int low = 0, high = length - 1;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (letters[mid] > target) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return letters[low];
    }
}


